package com.fx.algorithm.first;

/**
 * 合并两个有序链表
 * @author fx
 */
public class Leetcode21 {


    public ListNode mergeTwoLists3(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }else if (list2==null){
            return list1;
        }
       ListNode pro = new ListNode(-1);
       ListNode newNode = pro;
       while (list1!=null&&list2!=null){
           if (list1.val <= list2.val) {
               newNode.next = list1;
               newNode = newNode.next;
               list1=list1.next;
           }else{
               newNode.next = list2;
               newNode = newNode.next;
               list2=list2.next;
           }
       }
        newNode.next = list2==null?list1:list2;

        return pro.next;
    }


    public ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }else if (list2==null){
            return list1;
        }
        //if (list1 == list2) {
        //    return list1;
        //}
        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists2(list1.next,list2);
            return list1;
        }else{
            list2.next = mergeTwoLists2(list2.next,list1);
            return list2;
        }
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode first = null;
        ListNode nextNode = null;
        while(list1!=null||list2!=null){
            if(list1!=null&&list2!=null&&list1.val<=list2.val){
                nextNode = this.replace(nextNode,list1);
                if(first==null){
                    first = nextNode;
                }
                list1 = list1.next;
            }else if(list1==null||list2==null){
                if (list2 == null) {
                    nextNode = this.replace(nextNode,list1);
                    if(first==null){
                        first = nextNode;
                    }
                    list1 = list1.next;
                }else{
                    nextNode = this.replace(nextNode,list2);
                    if(first==null){
                        first = nextNode;
                    }
                    list2 = list2.next;
                }
            }else{
                nextNode = this.replace(nextNode,list2);
                if(first==null){
                    first = nextNode;
                }
                list2 = list2.next;
            }

        }
        if(nextNode!=null)nextNode.next = null;
        return first;
    }

    private ListNode replace(ListNode nextNode,ListNode node){
        if(nextNode==null){
            nextNode = node;
        }else{
            nextNode.next = node;
            nextNode = nextNode.next;
        }
        return nextNode;
    }

    public static void main(String[] args) {
        Leetcode21 leetcode21 = new Leetcode21();

        ListNode node = new ListNode(1);
        node.next=new ListNode(2);
        node.next.next=new ListNode(3);
        node.next.next.next=new ListNode(4);
        node.next.next.next.next=new ListNode(5);
        node.next.next.next.next.next=new ListNode(6);
        node.next.next.next.next.next.next=new ListNode(7);
        node.next.next.next.next.next.next.next=new ListNode(8);
        //
        ListNode node1 = new ListNode(1);
        node1.next=new ListNode(2);
        node1.next.next=new ListNode(3);
        node1.next.next.next=new ListNode(4);
        node1.next.next.next.next=new ListNode(5);
        node1.next.next.next.next.next=new ListNode(6);
        node1.next.next.next.next.next.next=new ListNode(7);
        node1.next.next.next.next.next.next.next=new ListNode(8);
        //
        //
        //prin( leetcode21.mergeTwoLists(node, node1));


        System.err.println(leetcode21.mergeTwoLists3(node,node1).toString());
        //prin(leetcode21.mergeTwoLists3(node,null));
        //prin(leetcode21.mergeTwoLists3(null,node1));
        //prin(node);
        //prin(node1);
    }
}
